DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2018.38

A Cut Tree Representation for Pendant Pairs

Authors: On-Hei S. Lo and Jens M. Schmidt

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract

Two vertices v and w of a graph G are called a pendant pair if the maximal number of edge-disjoint paths in G between them is precisely min{d(v),d(w)}, where d denotes the degree function. The importance of pendant pairs stems from the fact that they are the key ingredient in one of the simplest and most widely used algorithms for the minimum cut problem today. Mader showed 1974 that every simple graph with minimum degree delta contains Omega(delta^2) pendant pairs; this is the best bound known so far. We improve this result by showing that every simple graph G with minimum degree delta >= 5 or with edge-connectivity lambda >= 4 or with vertex-connectivity kappa >= 3 contains in fact Omega(delta |V|) pendant pairs. We prove that this bound is tight from several perspectives, and that Omega(delta |V|) pendant pairs can be computed efficiently, namely in linear time when a Gomory-Hu tree is given. Our method utilizes a new cut tree representation of graphs.

Cite as

On-Hei S. Lo and Jens M. Schmidt. A Cut Tree Representation for Pendant Pairs. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 38:1-38:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{lo_et_al:LIPIcs.ISAAC.2018.38,
  author =	{Lo, On-Hei S. and Schmidt, Jens M.},
  title =	{{A Cut Tree Representation for Pendant Pairs}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{38:1--38:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.38},
  URN =		{urn:nbn:de:0030-drops-99869},
  doi =		{10.4230/LIPIcs.ISAAC.2018.38},
  annote =	{Keywords: Pendant Pairs, Pendant Tree, Maximal Adjacency Ordering, Maximum Cardinality Search, Testing Edge-Connectivity, Gomory-Hu Tree}
}

Search Results

Documents authored by Lo, On-Hei S.

A Cut Tree Representation for Pendant Pairs

Abstract

Cite as

Thanks for your feedback!

Could not send message